#include <stdio.h>   // 包含标准输入输出库，用于printf等函数
#include <stdlib.h>  // 包含标准库，用于malloc等内存分配函数

// 定义二叉树节点存储的数据类型为char
typedef char ElemType;

// 定义二叉树节点结构体
typedef struct TreeNode
{
    ElemType data;          // 节点存储的数据
    struct TreeNode *lchid; // 指向左孩子节点的指针
    struct TreeNode *rchid; // 指向右孩子节点的指针
}TreeNode;

// 将TreeNode指针重定义为BinTree，表示二叉树的根节点指针
typedef TreeNode* BinTree;

// 用于构建二叉树的字符串，其中'#'表示空节点
// 字符串按前序遍历顺序排列：根节点->左子树->右子树
// 树用到的是栈结构
char str[] = "ABDH#K###E##CFI###G#J##"; 
int idx = 0;  // 全局索引，记录当前处理到字符串中的哪个字符

/**
 * 创建二叉树（前序遍历方式）
 * @param t 二叉树根节点的指针的指针（用于修改外部的根节点指针）
 */
void createTree(BinTree *t){
    ElemType ch;
    ch = str[idx++];  // 获取当前字符，并将索引后移一位

    // 如果当前字符是'#'，表示该位置为空节点
    if (ch == '#'){
        *t = NULL;
    }
    else{
        // 否则为有效节点，分配内存空间
        *t = (BinTree)malloc(sizeof(TreeNode));
        // 前序遍历逻辑：先处理当前节点，再递归处理左子树和右子树
        (*t)->data = ch;       // 设置当前节点的数据
        createTree(&(*t)->lchid); // 递归创建左子树
        createTree(&(*t)->rchid); // 递归创建右子树
    } 
}

/**
 * 前序遍历二叉树（递归实现）
 * 遍历顺序：根节点 -> 左子树 -> 右子树
 * @param T 二叉树的根节点指针
 */
void preOrder(BinTree T)
{
    if (T == NULL)  // 若节点为空，递归终止
    {
        return;
    }
    printf("%c",T->data);  // 访问根节点（输出数据）
    preOrder(T->lchid);    // 递归遍历左子树
    preOrder(T->rchid);    // 递归遍历右子树
}

/**
 * 中序遍历二叉树（递归实现）
 * 遍历顺序：左子树 -> 根节点 -> 右子树
 * @param T 二叉树的根节点指针
 */
void inOrder(BinTree T)
{
    if (T == NULL)  // 若节点为空，递归终止
    {
        return;
    }

    inOrder(T->lchid);     // 递归遍历左子树
    printf("%c",T->data);  // 访问根节点（输出数据）
    inOrder(T->rchid);     // 递归遍历右子树
}

/**
 * 后序遍历二叉树（递归实现）
 * 遍历顺序：左子树 -> 右子树 -> 根节点
 * @param T 二叉树的根节点指针
 */
void postOrder(BinTree T)
{
    if (T == NULL)  // 若节点为空，递归终止
    {
        return;
    } 
    postOrder(T->lchid);   // 递归遍历左子树
    postOrder(T->rchid);   // 递归遍历右子树
    printf("%c",T->data);  // 访问根节点（输出数据）
}

int main(){
    BinTree T;  // 定义二叉树的根节点指针

    createTree(&T);  // 调用函数创建二叉树

    // 分别执行三种遍历并输出结果
    preOrder(T);
    printf("\n");  // 换行，区分不同遍历结果
    inOrder(T);
    printf("\n");
    postOrder(T);
    printf("\n");

    return 0;  // 程序正常结束
}